#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using ll = int64_t;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::vector<ll> v;
    v.reserve(100000);
    ll tmp;
    while (std::cin >> tmp) {
        v.push_back(tmp);
    }
    if (v.empty()) {
        std::cout << "0\n0\n";
        return 0;
    }

    std::vector<ll> f(v.size() + 1, 0);
    f[1] = v[0]; // f[i]=最长不上升子序列中长度为i结尾的数字最大的
    ll maxdp = 1;
    
    for (ll i = 1; i < v.size(); i++) {
        ll h = v[i];
        ll l = 1, r = maxdp, ans = 0;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (f[mid] >= h) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (ans == 0) {
            f[1] = std::max(f[1], h);
        } else {
            ll nxt = ans + 1;
            if (nxt > maxdp) {
                maxdp = nxt;
                f[nxt] = h;
            } else {
                f[nxt] = std::max(f[nxt], h);
            }
        }
    }
    std::cout << maxdp << '\n';
    std::vector<ll> sys;
    sys.reserve(v.size());
    for (ll h : v) {
        auto it = std::lower_bound(sys.begin(), sys.end(), h);
        if (it == sys.end()) sys.push_back(h);
        else *it = h;
    }
    std::cout << sys.size() << '\n';
    return 0;
}
